import java.util.*;

public class 子集2 {
    //

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        dfs(nums,0,new int[nums.length],0,ret);
        return ret;
    }

    //采用分组的形式来进行决策
    //i是相同元素的第一位元素, path是存储的元素, size是path存储的个数, ret是返回值
    public void dfs(int[] nums,int i,int[] path,int size,List<List<Integer>> ret) {
        //当第一位元素发生越界的时候, 把path的元素全部都存储
        if (i == nums.length) {
            List<Integer> cur = new ArrayList<>();
            for(int k = 0;k < size;k++){
                cur.add(path[k]);
            }
            ret.add(cur);
        } else {
            //找到下一位元素的第一位元素
            int j = i + 1;
            while (j < nums.length && nums[i] == nums[j]) {
                j++;
            }
            //分组的元素从0开始,这个是第0个
            dfs(nums,j,path,size,ret);
            //遍历分组的元素1,2,3,....个
            for (; i < j; i++) {
                path[size++] = nums[i];
                dfs(nums,j,path,size,ret);
            }
        }
    }
}
